# 最短路径算法

maps = {"0":[("1", 4), ("7", 8)],
       "1":[("0", 4), ("2", 8), ("7", 11)],
       "2":[("1", 8), ("8", 2)],
      "8":[("2",2),("6",6),("7",7)],
      "7":[("0",8),("1",11),("8",7),("6",1)],
       "6":[("7", 1), ("8",6)]}
n = len(maps)
keys = maps.keys()
mark = ["0"]
juli = {f"{k}":999999 for k in keys}
juli["0"] = 0
pre = {f"{k}":None for k in keys}
pre["0"] = -1
def search(maps, juli, name):
  nodes = maps[name]
  for x in nodes:
    juli[x[0]] = min(juli[x[0]], juli[name]+ x[1])

name = "0"
while len(mark) < n:
    search(maps, juli, name)
    min_v = 999999
    for x in keys:
        if x not in mark and juli[x] < min_v:
            min_v = juli[x]
    for k, v in juli.items():
        if v == min_v:
            mark.append(k)
            name = k
            break